Many storage systems, and in particular databases and key-value storage systems, partition data according to a key-space and store the partitioned data among multiple servers. Such storage schemes are prevalent in cloud-based storage systems and cloud-based distributed processing systems.
In the context of an application that distributes its work across multiple computers, partitioning the data in a manner that results in a balanced work distribution among the working computers (e.g., servers) acting on the data is desirable. One common distribution scheme is to distribute the data randomly according to a data key. This is ubiquitous in web services, where the distribution of the data for the application is managed by a load balancer in front of a fleet of interchangeable application servers.
For example, consistent hashing can be used to initially balance the number of data items stored on each server. Thereafter, a peer-to-peer load balance algorithm can be used, where each server periodically chooses random other servers and tries to remain balanced with respect to these servers by shedding load to the other servers.